AtCoder Library
Various algorithms implemented on the AtCoder side Commentary AC'd all the way through the practice contest.
Anyway, I checked and about 1/3 to 1/2 of it was already implemented. I'll put it in the same directory structure as the ACLs and license it under the MIT license later.
The rest of the unimplemented ones will be implemented as soon as possible, since the officials say "this is a frequently used algorithm".
I'd like to see a Python implementation of the AtCoder Library, which is already full of ordinary algorithms (≈ just take it from yosupo judge or AOJ), and make it faster by using numpy/scipy/networkx or cython or something like that. I'd like to see something like this src I'm thinking that the All Submit time order ranking in the Practice Contest will be the place to compete for library speed.
I used to be into speeding things up with Numba and Cython, but recently I've come full circle and am interested in speeding things up with PyPy without sacrificing flexibility. Contents
A tree structure (also called a Binary Indexed Tree) that can efficiently both compute partial sums and update elements
The tree can be O(logN) summed or minimized when a fixed number of elements are updated by random access.
String Algorithm Assortment
752ms PyPy provisional first place z_algorithm
Math Algorithm Assortment
pow_mod
inv_mod
crt
In Python, the equivalent of np.convolve or something like that. Two Snuke couldn't fit on the int64, so I did it myself. Modint Structure that automatically takes mod
In Python, it would look pretty if you could achieve this with operator overloading, but I think the situations where this would be used are situations where you can't afford the overhead of a function call.
graph
For an undirected graph, add edges, determine whether vertices are connected, and then process in O(α(n)) time.
Strongly connected component decomposition of directed graphs
Determine if there exists an assignment that satisfies the logical expression of the form $ \bigvee (x_{i0} = v_{i0} \wedge x_{i1} = v_{i1}), and if so, obtain one of these assignments
You can practice here.
Python Related Articles
---
This page is auto-translated from /nishio/AtCoder Library using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.